package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.HashMap;

public class a3第k小查找 {
	public static void main(String[] args) {
		int[] arr = new int[] {6,8,7,9,5,4,3,6};//3，4，5，6，6，7，8，9
		long before = System.currentTimeMillis();
		int selectK = selectK(arr, 0, arr.length - 1, 2);
		util.Util.duration(before);
		System.out.println(selectK);
	}
	
	/**
	 * 第k小查找
	 * k从1开始，代表的是元素的位置(而不是元素的索引)
	 * O(N)
	 * @param arr
	 * @param p
	 * @param r
	 * @param k
	 * @return
	 */
	public static int selectK(int[] arr, int p, int r, int k) {//使用老师的递归算法思想
		if (p <= r) {//如果数组片段,起始元素索引大于末尾元素索引，那么直接返回没找到-1
			//这里必须<=;单单<的话，第二个元素和最后一个元素是无法被判断的
			int[] q = partition(arr, p, r);
			int locationLeft = q[0] - p + 1;
			int locationRight = q[1] - p + 1;
			if (locationLeft <= k && k <= locationRight) {
				return arr[q[0]];
			} else if (k < locationLeft) {
				return selectK(arr, p, q[0] - 1, k);
			} else {
				return selectK(arr, q[1] + 1, r, k - locationRight);
			}
		} else {
			return -1;
		}
	}
	
	public static int[] partition(int[] arr, int p, int r) {
		int equalLeft = p + 1;
		int small = p + 1;
		int bigger = r;
		int midElementIndex = getMedian(arr, p, r);
		swap(arr, p, midElementIndex);
		int piovet = arr[p];
		int[] equals = new int[2];
		while (small <= bigger) {
			while (small <= bigger && arr[small] <= piovet) {
				if (arr[small] < piovet && small == equalLeft) {
					small++;
					equalLeft++;
				} else if (arr[small] < piovet && small != equalLeft) {
					swap(arr, small, equalLeft);
					small++;
					equalLeft++;
				} else {
					small++;
				}
			}
			while (small <= bigger && arr[bigger] > piovet) {
				bigger--;
			}
			if (small < bigger) {
				swap(arr, small, bigger);
			}
		}
		swap(arr, p, equalLeft - 1);
		equals[0] = equalLeft - 1;
		equals[1] = bigger;
		return equals;
	}
	
	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> mediansOfValueAndIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + 5 * i, r);
				medians[indexOfMedians++] = arr[(p + 5 * i + r) >>> 1];
				mediansOfValueAndIndex.put(arr[(p + 5 * i + r) >>> 1], (p + 5 * i + r) >>> 1);
			} else {
				insertSort(arr, p + 5 * i, p + 5 * i + 4);
				medians[indexOfMedians++] = arr[p + 5 * i + 2];
				mediansOfValueAndIndex.put(arr[p + 5 * i + 2], p + 5 * i + 2);
			}
		}
		insertSort(arr, 0, groupSize - 1);
		return mediansOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(int[] arr, int p, int r) {
		int before_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];//不能删除此行；此行在交换前把arr[i]的值保存在value_i中
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;//在交换后，再把这个值赋给目标位置
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
